/*
 * @lc app=leetcode.cn id=227 lang=cpp
 *
 * [227] 基本计算器 II
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution
{
    bool isNum(char c)
    {
        return c >= '0' && c <= '9';
    }

    string removeSpace(string &s)
    {
        string ret;

        for (auto c : s)
        {
            if (c != ' ')
                ret += c;
        }

        return ret;
    }

    int atoi_(int i, int j, const string& s)
    {
        int ret = 0;
        while(i < j)
        {
            ret *= 10;
            ret += s[i++] - '0';
        }
        return ret;
    }

public:
    int calculate(string s)
    {
        s = removeSpace(s);
        vector<int> stac;
        vector<char> ops;
        int i = 0, j = 1;
        while (true)
        {
            while (j < s.size() && isNum(s[j]))
                ++j;

            int b = atoi_(i, j, s);

            if (ops.size())
            {
                switch (*(ops.end() - 1))
                {
                case '*':
                {
                    int a = *(stac.end()-1);
                    *(stac.end() - 1) = (a * b);
                    ops.erase(ops.end() - 1);
                    break;
                }

                case '/':
                {
                    int a = *(stac.end()-1);
                    *(stac.end() - 1) = (a / b);
                    ops.erase(ops.end() - 1);
                    break;
                }
                default:
                    stac.push_back(b);
                    break;
                }
            }
            else
            {
                stac.push_back(b);
            }

            if (j == s.size())
            {
                break;
            }

            ops.push_back(s[j]);

            i = j + 1;
            j = i + 1;
        }

        for(int i = 0; i < ops.size(); i++)
        {
            switch (ops[i])
            {
            case '+':
                stac[i+1] += stac[i];
                break;
            case '-':
                stac[i+1] = stac[i] - stac[i+1];
                break;
            default:
                break;
            }
        }

        return *(stac.end() - 1);
    }
};

// int main(int argc, char const *argv[])
// {
//     cout << Solution().calculate("3+2*2") << endl;
//     return 0;
// }

// @lc code=end
